#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
#define OK 1
#define ERROR 0

typedef struct {
	ElemType *elem;
	int length;
	int listsize;
} SqList;

int InitList_Sq(SqList *L)
{
	L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (L->elem == NULL) return ERROR;
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}

void DestroyList(SqList *L)
{
	if (L == NULL) return;
	if (L->elem) free(L->elem);
	L->elem = NULL;
	L->length = 0;
	L->listsize = 0;
}

/* 打印顺序表 */
void PrintList(const SqList *L)
{
	if (L == NULL) return;
	printf("length=%d, listsize=%d\n", L->length, L->listsize);
	for (int i = 0; i < L->length; ++i) {
		if (i) printf(" ");
		printf("%d", L->elem[i]);
	}
	printf("\n");
}

/* 将两个非递减有序的顺序表 A 和 B 合并为一个非递减有序顺序表 C
   约定：C 必须由函数分配存储空间（或保证有足够空间）。
*/
int MergeList(const SqList *A, const SqList *B, SqList *C)
{
	if (A == NULL || B == NULL || C == NULL) return ERROR;

	int na = A->length;
	int nb = B->length;
	/* 为 C 分配恰好需要的空间 */
	C->elem = (ElemType *)malloc((na + nb) * sizeof(ElemType));
	if (C->elem == NULL) return ERROR;
	C->listsize = na + nb;

	int i = 0, j = 0, k = 0;
	while (i < na && j < nb) {
		if (A->elem[i] <= B->elem[j]) {
			C->elem[k++] = A->elem[i++];
		} else {
			C->elem[k++] = B->elem[j++];
		}
	}
	while (i < na) C->elem[k++] = A->elem[i++];
	while (j < nb) C->elem[k++] = B->elem[j++];

	C->length = k;
	return OK;
}

/* 示例：用两个数组演示合并 */
int main(void)
{
	SqList A, B, C;
	if (InitList_Sq(&A) == ERROR || InitList_Sq(&B) == ERROR) {
		fprintf(stderr, "InitList_Sq failed\n");
		return 1;
	}

	/* 初始化 A 和 B 为有序数组 */
	int a_vals[] = {10, 20, 30, 40, 50};
	int b_vals[] = {15, 25, 35, 45};
	int na = sizeof(a_vals) / sizeof(a_vals[0]);
	int nb = sizeof(b_vals) / sizeof(b_vals[0]);

	/* 确保容量足够（InitList 已分配足够，但演示以通用方式复制数据） */
	for (int i = 0; i < na; ++i) A.elem[i] = a_vals[i];
	A.length = na;

	for (int i = 0; i < nb; ++i) B.elem[i] = b_vals[i];
	B.length = nb;

	printf("A: "); PrintList(&A);
	printf("B: "); PrintList(&B);

	if (MergeList(&A, &B, &C) != OK) {
		fprintf(stderr, "MergeList failed\n");
		DestroyList(&A);
		DestroyList(&B);
		return 1;
	}

	printf("Merged C: "); PrintList(&C);

	DestroyList(&A);
	DestroyList(&B);
	DestroyList(&C);
	return 0;
}